Not Applicable.
This invention relates to generally to a method and apparatus for transmitting of data on a communications network. More specifically, this invention relates to timely forwarding and delivery of data over the network and to their destination nodes. Consequently, the end-to-end performance parameters, such as, loss, delay and jitter, have either deterministic or probabilistic guarantees.
The proliferation of high-speed communications links, fast processors, and affordable, multimedia-ready personal computers brings about the need for wide area networks that can carry real-time data, like telephony and video. However, the end-to-end transport requirements of real-time multimedia applications present a major challenge that cannot be solved satisfactorily by current networking technologies. Such applications as video teleconferencing, and audio and video group (many-to-many) multicasting generate data at a wide range of bit rates and require predictable, stable performance and strict limits on loss rates, end-to-end delay bounds, and delay variations (xe2x80x9cjitterxe2x80x9d). These characteristics and performance requirements are incompatible with the services that current circuit and packet switching networks can offer.
Circuit-switching networks, which are still the main carrier for real-time traffic, are designed for telephony service and cannot be easily enhanced to support multiple services or carry multimedia traffic. Its synchronous byte switching enables circuit-switching networks to transport data streams at constant rates with little delay or jitter. However, since circuit-switching networks allocate resources exclusively for individual connections, they suffer from low utilization under bursty traffic. Moreover, it is difficult to dynamically allocate circuits of widely different capacities, which makes it a challenge to support multimedia traffic. Finally, the synchronous byte switching of SONET, which embodies the Synchronous Digital Hierarchy (SDH), requires increasingly more precise clock synchronization as the lines speed increases [John C. Bellamy, xe2x80x9cDigital Network Synchronizationxe2x80x9d, IEEE Communications Magazine, April 1995, pages 70-83].
Packet switching networks like IP (Internet Protocol)xe2x80x94based Internet and Intranets [see, for example, A. Tannebaum, Computer Networks (3rd Ed) Prentice Hall, 1996] and ATM (Asynchronous Transfer Mode) [see, for example, Handel et al., ATM Networks: Concepts, Protocols, and Applications (2nd Ed.) Addison-Wesley, 1994] handle bursty data more efficiently than circuit switching, due to their statistical multiplexing of the packet streams. However, current packet switches and routers operate asynchronously and provide best effort service only, in which end-to-end delay and jitter are neither guaranteed nor bounded. Furthermore, statistical variations of traffic intensity often lead to congestion that results in excessive delays and loss of packets, thereby significantly reducing the fidelity of real-time streams at their points of reception.
Efforts to define advanced services for both IP and ATM have been conducted in two levels: (1) definition of service, and (2) specification of methods for providing different services to different packet streams. The former defines interfaces, data formats, and performance objectives. The latter specifies procedures for processing packets by hosts and switches/routers. The types of services that defined for ATM include constant bit rate (CBR), variable bit rate (VBR) and available bit rate (ABR).
The methods for providing different services under packet switching fall under the general title of Quality of Service (QoS). Prior art in QoS can be divided into two parts: (1) traffic shaping with local timing without deadline scheduling, for example [Demers et al., xe2x80x9cAnalysis and Simulation Of A Fair Queuing Algorithmxe2x80x9d, ACM Computer Communication Review (SIGCOMM""89), pages 3-12, 1989; S. J. Golestani, xe2x80x9cCongestion-Free Communication In High-Speed Packet Networksxe2x80x9d, IEEE Transcripts on Communications, COM-39(12):1802-1812, December 1991; Parekh et al., xe2x80x9cA Generalized Processor Sharing Approach To Flow Controlxe2x80x94The Multiple Node Casexe2x80x9d, ACM Transactions on Networking, 2(2):137-150, 1994], and (2) traffic shaping with deadline scheduling, for example [Ferrari et al., xe2x80x9cA Scheme For Real-Time Channel Establishment In Wide-Area Networksxe2x80x9d, IEEE Journal on Selected Areas in Communication, SAC-8(4):368-379, April 1990]. Both of these approaches rely on manipulation of local queues by each router with little or no coordination with other routers. These approaches have inherent limitations when used to transport real-time streams. When traffic shaping without deadline scheduling is configured to operate at high utilization with no loss, the delay and jitter are inversely proportional to the connection bandwidth, which means that low rate connections may experience large delay and jitter inside the network. In traffic shaping with deadline scheduling the delay and jitter are controlled at the expense of possible congestion and loss.
The real-time transport protocol (RTP) [H. Schultzrinne et. al, xe2x80x9cRTP: A Transport Protocol for Real-Time Applicationxe2x80x9ds, IETF Request for Comment RFC1889, January 1996] is a method for encapsulating time-sensitive data packets and attaching to the data time related information like time stamps and packet sequence number. RTP is currently the accepted method for transporting real-time streams over IP internetworks and packet audio/video telephony based on ITU-T H.323.
One approach to an optical network that uses synchronization was introduced in the synchronous optical hypergraph [Y. Ofek, xe2x80x9cThe Topology, Algorithms And Analysis Of A Synchronous Optical Hypergraph Architecturexe2x80x9d, Ph.D. Dissertation, Electrical Engineering Department, University of Illinois at Urbana, Report No. UIUCDCS-R-87-1343, May 1987], which also relates to how to integrate packet telephony using synchronization [Y. Ofek, xe2x80x9cIntegration Of Voice Communication On A Synchronous Optical Hypergraphxe2x80x9d, IEEE INFOCOM""88, 1988]. In the synchronous optical hypergraph, the forwarding is performed over hyper-edges, which are passive optical stars. In [Li et al., xe2x80x9cPseudo-Isochronous Cell Switching In ATM Networksxe2x80x9d, IEEE INFOCOM""94, pages 428-437, 1994; Li et al., xe2x80x9cTime-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworkingxe2x80x9d, IEEE INFOCOM""96, 1996] the synchronous optical hypergraph idea was applied to networks with an arbitrary topology and with point-to-point links. The two papers [Li et al., xe2x80x9cPseudo-Isochronous Cell Switching In ATM Networksxe2x80x9d, IEEE INFOCOM""94, pages 428-437, 1994; Li et al., xe2x80x9cTime-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworkingxe2x80x9d, IEEE INFOCOM""96, 1996] provide an abstract (high level) description of what is called xe2x80x9cRISC-like forwardingxe2x80x9d, in which a packet is forwarded, with little if any details, one hop every time frame in a manner similar to the execution of instructions in a Reduced Instruction Set Computer (RISC) machine.
In accordance with the present invention, a method is disclosed providing virtual pipes that carry real-time traffic over packet switching networks with widely varying link speeds, while guaranteeing end-to-end performance. The method combines the advantages of both circuit and packet switching. It provides for allocation for the exclusive use of predefined connections and for those connections it guarantees loss free transport with low delay and jitter. When predefined connections do not use their allocated resources, other non-reserved data packets can use them without affecting the performance of the predefined connections.
Under the aforementioned prior art methods for providing packet switching services, switches and routers operate asynchronously. The present invention provides real-time services by synchronous methods that utilize a time reference that is common to the switches and end stations comprising a wide area network. The common time reference can be realized by using UTC (Coordinated Universal Time), which is globally available via, for example, GPS (Global Positioning Systemxe2x80x94see, for example: [Peter H. Dana, xe2x80x9cGlobal Positioning System (GPS) Time Dissemination for Real-Time Applicationsxe2x80x9d, Real-Time Systems, 12, pp. 9-40, 1997]. By international agreement, UTC is the same all over the world. UTC is the scientific name for what is commonly called GMT (Greenwich Mean Time), the time at the 0 (root) line of longitude at Greenwich, England. In 1967, an international agreement established the length of a second as the duration of 9,192,631,770 oscillations of the cesium atom. The adoption of the atomic second led to the coordination of clocks around the world and the establishment of UTC in 1972. The Time and Frequency Division of the National Institute of Standards and Technologies (NIST) (see http://www.boulder.nist.gov/timefreq) is responsible for coordinating UTC with the International Bureau of Weights and Measures (BIPM) in Paris.
UTC timing is readily available to individual PCs through GPS cards. For example, TrueTime, Inc.""s (Santa Rosa, Calif.) PCI-SG provides precise time, with zero latency, to computers that have PCI extension slots. Another way by which UTC can be provided over a network is by using the Network Time Protocol (NTP) [D. Mills, xe2x80x9cNetwork Time Protocolxe2x80x9d (version 3) IETF RFC 1305]. However, the clock accuracy of NTP is not adequate for inter-switch coordination, on which this invention is based.
In accordance with the present invention, the synchronization requirements are independent of the physical link transmission speed, while in circuit switching the synchronization becomes more and more difficult as the link speed increases.
In accordance with the present invention, timing information is not used for routing, and therefore, in the Internet, for example, the routing is done using IP addresses or an IP tag/label.
In accordance with the present invention, timing information is provided by using a Common Time Reference (CTR) signal, one such source is the above mentioned GPS. CTR is used for the timely forwarding over links with plurality of different time frame intervals: TF1, TF2, and so on. Employing different time frame intervals are useful in heterogeneous networks with widely varying link speeds, as shown in the following table. That is, the number of bytes that can be transmitted during one time frame of, say, 500/125/12.5 microseconds changes according to the link capacity.
In accordance with the present invention, the Internet xe2x80x9cbest effortxe2x80x9d data packet forwarding strategy is integrated into the system. Furthermore, if the transmission of a xe2x80x9cbest effortxe2x80x9d data packet does not complete at the end of a time frame, a real-time data packet can have a novel time-driven non-destructive preemptive priority. This implies that the transmission of a xe2x80x9cbest effortxe2x80x9d data packet is stopped while real-time data packets are transmitted, and will resume after all scheduled real-time data packets have been transmitted. The time-driven preemption method used in this invention is novel since the preemption priority is given at a certain time, which is derived from the common time reference.